package 排序;

public class 数组中的逆序对 {
    //这个是用归并排序思想
    //看代码和题目好好理解就行了https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0
    int cnt = 0;
    public int InversePairs(int [] array) {
        if (array.length!=0){
            divide(array,0,array.length-1);
        }
        return cnt;
    }

    private void divide(int[] array, int start, int end) {
        //递归停止条件
        if (start>=end) return;
        //取中
        int mid = start+(end-start)/2;
        //分
        divide(array,start,mid);
        divide(array,mid+1,end);
        //治
        //在递归到不能递后面才执行这一句。简而言之就是每个递归分解成最小块了
        merge(array,start,mid,end);
    }

    private void merge(int[] array, int start, int mid, int end) {
        //临时数组
        int[] tmp = new int[end - start+1];
        //
        int i = start;
        int j = mid+1;
        int k =0;
        while (i<=mid&&j<=end){
            if (array[i]<=array[j]){
                tmp[k++] = array[i++];
            }else {
                tmp[k++] = array[j++];
                cnt = (cnt+mid-i+1)%1000000007;
            }
        }
        //未遍历完的直接放在右侧
        while (i<=mid){
            tmp[k++] = array[i++];
        }
        while (j<=end){
            tmp[k++] = array[j++];
        }
        //按临时数组的值覆盖原来的数组
        for (int l = 0; l <array.length; l++) {
            array[start+l] = tmp[l];
        }
    }
}
